﻿#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

// 节点对应的结构体
typedef struct Node
{
    int num;            // 每个节点中存储的数据，可以有多个
    struct Node* pNext; // 用于保存下一个节点(结构体)的指针
}NODE;

/* 
* 函数功能：  创建一个新节点
* int n：     当前节点的数据
* 返回类型：  成功:返回当前节点的首地址, 失败:NULL
*/
NODE* createNode(int n)
{
    // 创建新节点
    NODE* pNew = (NODE*)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
        printf("createNode %d fail: %s!\n", n, strerror(errno));
        return NULL;
    }

    // 初始化新节点中的成员变量
    pNew->num = n;
    pNew->pNext = NULL;

    // 返回当前节点的首地址
    return pNew;
}

/*
* 函数功能：  删除整个链表(从前向后删除)
* NODE* head：链表首地址
* 返回类型：  无
*/
void distroyList(NODE* head)
{
    // 获取首节点指针
    NODE* p = head;

    // 判断当前节点指针是否为空
    while (p != NULL)
    {
        // 当删除第一个节点时
        // 先将首节点指针后移
        head = p->pNext;

        // 删除第一个节点
        free(p);

        // 移动循环变量到新链表的首节点
        p = head;
    }
}

/*
* 函数功能：  输出整个链表
* NODE* head：链表首地址
* 返回类型：  无
*/
void displayList(NODE* head)
{
    NODE* p = head;
    while (p != NULL)
    {
        printf("%d ", p->num);
        p = p->pNext;
    }
    printf("\n");
}

// 将节点插入链表中：头插法
NODE* inserthead(NODE* head,int data)
{
    NODE * p = createNode(data);
    p->num = data;

    if(head == NULL)
        return p;

    p->pNext = head;
    return p;
}

// 将节点插入链表中：尾插法
NODE* insertlast(NODE *head,int data)
{
    NODE * p = createNode(data);
    p->num = data;
    NODE * cp = head;
    while(cp->pNext != NULL)
    {
        cp = cp->pNext;
    }
    cp->pNext = p;
    p->pNext = NULL;
    return head;
}

// 将节点插入链表中：中间插入
NODE* insertmiddle(NODE* head, int data) 
{
    NODE *newNode = createNode(data);

    if (head == NULL) 
    {
        return newNode;
    }

    NODE *slow = head;
    NODE *fast = head;
    NODE *prev = NULL; // 用于记录 slow 的前一个节点

    // 快指针每次走 2 步，慢指针每次走 1 步
    while (fast != NULL && fast->pNext != NULL) 
    {
        fast = fast->pNext->pNext;
        prev = slow;
        slow = slow->pNext;
    }

    // 插入新节点
    if (prev == NULL) 
    {
        // 链表长度 <= 1，直接插在头部
        newNode->pNext = head;
        return newNode;
    } else 
    {
        newNode->pNext = slow;
        prev->pNext = newNode;
    }

    return head;
}

int main()
{
    // 用于记录当前链表中首节点的地址
    NODE* pHead = NULL;

    // 将节点插入链表中：头插法
    pHead = inserthead(pHead,4);
    pHead = inserthead(pHead,3);
    pHead = inserthead(pHead,2);
    pHead = inserthead(pHead,1);

    // 将节点插入链表中：尾插法
    pHead = insertlast(pHead,4);
    pHead = insertlast(pHead,3);
    pHead = insertlast(pHead,2);
    pHead = insertlast(pHead,1);

    // 将节点插入链表中：中间插入
    pHead = insertmiddle(pHead,5);


    displayList(pHead);

    distroyList(pHead);

    return 0;
}